/*
* leetcode 5. 最长回文子串
*
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
* */
/*

* */
import java.util.*;

class Solution {
    public String longestPalindrome(String s) {
        int n=s.length(),maxlen=0,l=0,r=0;
        boolean[][] dp=new boolean[n][n];
        char[] cs=s.toCharArray();
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(cs[i]==cs[j]&&(j-i<=1||dp[i+1][j-1]))dp[i][j]=true;
                if(dp[i][j]&&j-i+1>maxlen){
                    maxlen=j-i+1;
                    l=i;
                    r=j;
                }
            }
        }
        return s.substring(l,r+1);
    }
}